package Aula7;

import java.util.ArrayList;

public class NumeroCaminhosImpl implements NumeroCaminhos {

	public boolean[][] matrizGrafo;

	public NumeroCaminhosImpl() {
		super();
	}

	public int caminhos(int origem, int destino) {
		ArrayList<Integer> lista = new ArrayList<Integer>();
		int vertice, count = 0;

		lista.add(origem);
		while (!lista.isEmpty()) {
			vertice = lista.get(0);
			for (int coluna = 0; coluna < matrizGrafo[vertice].length; coluna++) {
				if (matrizGrafo[vertice][coluna]) {
					if (coluna == destino) {
						count++;
					} else {
						lista.add(coluna);
					}
				}
			}
			lista.remove(0);
		}
		return count;
	}

	public void preencherGrafo(boolean[][] matrizGrafo, int tamanho) {
		this.matrizGrafo = matrizGrafo;

	}

	public static void main(String[] args) {
		NumeroCaminhos g = new NumeroCaminhosImpl();

		boolean[][] matriz = { { false, true, true, false },
				{ false, false, false, true }, { false, false, false, true },
				{ false, false, false, false } };
		int tamanhoMatriz = 4;
		g.preencherGrafo(matriz, tamanhoMatriz);

		System.out.println("Numero de caminhos entre 0 e 1: "
				+ g.caminhos(0, 1));

		System.out.println("Numero de caminhos entre 0 e 3: "
				+ g.caminhos(0, 3));
	}
}
